NewOS. Легка, відкрита операційна система

Журнал Dr. Dobb's, грудень 2001
Автор: Тревіс К. Гайзельбрехт
Тревіс — інженер із розробки прошивок у компанії Danger Research Inc. З ним можна зв’язатися за адресою [email protected].

NewOS — це безкоштовна операційна система з відкритим вихідним кодом, легка за своєю природою, створена з нуля для роботи на різноманітних платформах. На цьому етапі проєкту NewOS є переважно ядром із мінімальною взаємодією з користувацьким простором. Проте в міру розвитку проєкту користувацькі програми та функції будуть удосконалюватися.

Розпочинаючи проєкт, я мав на меті низку дизайнерських цілей, більшість із яких є типовими для сучасних операційних систем:

Випереджувальна багатозадачність/багатопоточність.
Симетрична багатопроцесорність (підтримка кількох процесорів).
Повна реентрантність ядра.
Сучасна система віртуальної пам’яті з ізольованою пам’яттю.
Модульний рівень файлової системи.
Незалежність від архітектури, легка адаптація до різних платформ.
Ядро написане переважно мовою C із додаванням асемблера. Користувацькі програми теоретично можна створювати майже будь-якою мовою, але наразі підтримується лише C та асемблер.

На момент написання статті я адаптував NewOS для поширених платформ на базі процесорів Intel і AMD, а також для ігрової консолі Sega Dreamcast, яка працює на процесорі Hitachi SH-4. Триває робота над портуванням на системи з процесорами MIPS і UltraSPARC, а також є плани (хоча поки без значного прогресу) щодо адаптації для систем із процесорами Alpha та Motorola 68030.

Середовище збирання проєкту базується на інструментах розробки GNU: gcc, make та binutils. Ці інструменти можна зібрати для більшості поширених операційних систем і налаштувати для роботи з будь-якою платформою, яка має реальні шанси на адаптацію. Проєкт регулярно збирається на BeOS, Linux, FreeBSD, Solaris, Irix і Windows NT. Наразі цільовими процесорами є Intel IA-32 та Hitachi SH-4. Гнучкість цих інструментів значно сприяє розвитку проєкту.

Основні особливості дизайну

NewOS реалізує традиційну модель із кількома потоками на процес. Кожен процес визначається як набір потоків, що спільно використовують єдиний адресний простір, файлові дескриптори та права доступу. Існує спеціальний процес, до якого належать усі потоки ядра.

Перший потік у процесі має дещо відмінне трактування порівняно з іншими. Цей потік вважається основним, і процес не може існувати без нього. Якщо основний потік з будь-якої причини припиняє роботу, весь процес завершується. Для однопотокових програм це не має значення, але в багатопотокових додатках основний потік необхідно підтримувати активним, інакше програма може швидко завершитися простим виходом із цього потоку. Наразі немає можливості змінити основний потік, але це можна реалізувати за потреби.

Створення та видалення процесів у NewOS відрізняється від UNIX у багатьох аспектах. Використана модель не базується на традиційному підході UNIX із fork/exec, а є простішою: процес просто створює інший за допомогою виклику proc_create_proc без складнощів, пов’язаних із успадкуванням файлових дескрипторів чи копіюванням деталей адресного простору, з якими стикаються або які мають традиційні системи UNIX — залежно від вашої точки зору. Це, однак, накладає певні обмеження на гнучкість системи, і в майбутньому модель може бути розширена. У Лістингу 1 наведено оголошення функцій для API потоків.

Потоки створюються подібним чином: виклик просто створює новий потік у цільовому адресному просторі. Зазвичай це буде поточний адресний простір, але можливо також створити потік як частину процесу ядра для системних завдань тощо.

Коли потік завершується або виходить із системним викликом sys_exit, користувацький простір і стек ядра, створені для нього, знищуються, а потік видаляється з процесу разом із усіма пов’язаними структурами. Я подбав про те, щоб потік, який завершується, міг повністю прибрати за собою. Це проявляється в тому, як він видаляє власний стек ядра: останнім кроком потік перемикається на тимчасовий стек і видаляє старий. Багато інших операційних систем обходять цю складність, використовуючи робочий потік для очищення стека ядра, але це може призводити до вузьких місць у системі з високим навантаженням. Останній потік у процесі повертає всі ресурси процесу та видаляє його останні сліди.

Кожен потік завершується або виходить із кодом повернення. Цей код передається в системний виклик sys_exit, або ядро призначає його, якщо потік був убитий. Будь-який потік у системі може отримати код повернення іншого потоку, якщо він заблокований на завершення цього потоку за допомогою системного виклику sys_thread_wait_on_thread. Адреса повернення цієї функції є адресою повернення потоку. Адреса повернення цілого процесу — це просто адреса повернення основного потоку процесу. Системний виклик sys_proc_wait_on_proc є особливим випадком sys_thread_wait_on_thread, який блокується на основному потоці. Для реалізації блокування на потоці з кожним потоком асоціюється семафор із початковим значенням 0, тож будь-який потік, що намагається його отримати, одразу блокується. Коли потік завершується, семафор знищується, звільняючи всі потоки, що на ньому заблоковані. Спеціальний аргумент може передаватися функції знищення семафора, щоб передати його значення всім заблокованим потокам. Це дозволяє передавати код повернення заблокованим потокам без необхідності обробляти залишки записів про завершення чи "зомбі-процеси".

Служби таймерів

NewOS використовує дещо інший механізм таймерів, ніж багато традиційних UNIX-систем. Традиційний метод відстеження часу полягає в тому, щоб таймер спрацьовував із фіксованим інтервалом, а в обробнику переривання таймера лічильник поточного часу збільшувався на значення інтервалу. Система NewOS є динамічнішою та використовує цікавіші функції процесорів, наявні в багатьох сучасних архітектурах.

Код таймерів у NewOS простий і спирається на кілька особливостей багатьох архітектур. По-перше, платформа повинна мати принаймні один змінний таймер, бажано по одному на кожен процесор. Крім того, платформа повинна мати можливість визначати системний час із достатньою точністю відносно певної фіксованої точки в минулому без використання самого системного таймера. Достатня точність — бажано одна мілісекунда або менше. Наприклад, на архітектурі Intel IA-32 системний час можна визначити, зчитавши регістр підрахунку інструкцій процесора за допомогою команди rdtsc. Вона повертає 64-бітне значення — лічильник кількості циклів процесора з певної довільної точки в минулому, зазвичай із моменту увімкнення. Потім до цього значення застосовуються математичні обчислення для переведення в мікросекунди з моменту завантаження ОС. Інші архітектури мають подібну функціональність або її емуляцію.

Черга таймерів — це список подій, відсортований за абсолютним системним часом, коли подія має спрацювати. Коли системний таймер спрацьовує, перевіряється початок цього списку, його запланований час порівнюється з поточним, і подія виконується, якщо її час минув. Цей процес повторюється, поки початок списку не буде готовий до спрацювання. Потім планується нове переривання таймера на час початку нового списку. Завдяки цьому методу системний таймер може бути точним до мікросекунди, а зайві спрацювання таймера, що витрачають цикли процесора, не відбуваються. У Лістингу 2 наведено оголошення функцій і структур для модуля таймерів.

Подія таймера визначається просто як указівник на функцію зворотного виклику з необов’язковим аргументом-указівником, яку потрібно викликати. Система переплановує, якщо зворотний виклик повертає INT_RESCHEDULE, так само, як будь-який інший обробник переривань змушує перепланувати. Це використовується планувальником потоків для організації перепланування в кінці кванта поточного потоку.

Окрема черга таймерів із окремим таймером ведеться для кожного процесора, спрацьовуючи незалежно один від одного. Коли подія запланована, вона додається до списку того процесора, який викликав timer_set_event. Окремий список ведеться, тому що в деяких випадках таймер має спрацювати на тому самому процесорі, наприклад, для події перепланування.

Примітиви блокування

Щоб усе було просто, NewOS побудовано навколо єдиного типу примітива блокування — семафора з множинним лічильником. Цей тип семафора складається з лічильника та черги потоків. Лічильник ініціалізується значенням, яке задає користувач під час створення семафора. Ця модель семафорів значною мірою запозичена з дизайну семафорів, використаного в BeOS.

Семафор працює так: коли потік отримує його за допомогою sem_acquire, передається значення лічильника. Лічильник семафора зменшується на це значення. Якщо нове значення лічильника стає меншим за 0, потік, що отримав семафор, блокується, потрапляючи до черги очікування семафора. Значення, на яке потік заблокував семафор, зберігається в структурі потоку. Коли потік звільняє семафор із певним значенням, лічильник семафора збільшується на передане значення, і відповідна кількість заблокованих потоків із черги очікування звільняється. У Лістингу 3 наведено API семафорів.

Семафор також можна отримати з тайм-аутом. Це дозволяє виклику sem_acquire повернутися після заданого часу, якщо семафор не вдається отримати. Це реалізовано шляхом установлення події таймера, яка спрацьовує та звільняє викликаючий потік із черги семафора. За допомогою цієї функції код потоків тимчасово призупиняє потік від імені thread_snooze, отримуючи зарезервований семафор із початковим значенням нуль із відповідним тайм-аутом.

Коли семафор видаляється, усі потоки, заблоковані на ньому, негайно звільняються. Якщо sem_delete викликається з необов’язковим аргументом коду повернення, а заблоковані потоки отримали семафор за допомогою іншої форми sem_acquire, код повернення записується в змінну в структурах заблокованих потоків під час їхнього пробудження, і ці потоки повертаються з кодом повернення. Ця функціональність використовується для отримання коду повернення потоку чи процесу.

Симетрична багатопроцесорність

Реалізація симетричної багатопроцесорності (SMP) виявилася відносно простою, оскільки вона враховувалася з самого початку проєкту. Її легше впровадити, якщо дизайн усієї системи враховує це з самого початку, а належне блокування розміщується в ключових місцях.

Основні деталі реалізації підтримки SMP, які потребують певного часу, — це правильне блокування ключових структур даних і міжпроцесорні переривання.

Блокування структур даних від пошкодження кількома процесорами забезпечується використанням "спінлоків" — простого примітива блокування, що складається з одного булевого значення, у цьому випадку цілого числа. Отримання спінлока полягає у використанні атомарної операції "тест і встановлення" процесора для спроби встановити блокування в 1, яка проходить лише якщо значення раніше було 0. Якщо значення вже 1, потік просто "крутиться" в циклі, доки воно не стане 0. Звільнення спінлока виконується простим установленням значення блокування в 0. У Лістингу 4 наведено оголошення функцій спінлоків.

Оскільки будь-який процесор, що крутиться на спінлоці, витрачає цикли процесора та цикли шини пам’яті, спінлоки потрібно утримувати якомога коротший час. Вони використовуються переважно в областях ядра, де немає інших засобів синхронізації або де перепланування неприпустиме, наприклад, у коді планування чи реалізації семафорів. Через природу спінлока їх можна отримувати та звільняти лише з відключеними перериваннями, адже перепланування з утримуваним спінлоком могло б призвести до катастрофи, якби блокування було повторно отримано з іншої причини.

Міжпроцесорні переривання (ICI) реалізувати відносно легко. Самі переривання виконуються залежно від архітектури. Після спрацювання переривання код ICI перевіряє "поштову скриньку" на повідомлення для перерваного процесора, виконує дію, визначену в повідомленні, і повертається. Повідомлення ICI варіюються від простого перепланування потоків до очищення сторінок блоку керування пам’яттю чи негайної зупинки процесора. Для кожного процесора є окрема поштова скринька, а також глобальна скринька для всіх процесорів для широкомовних повідомлень.

Керування пам’яттю

Цілі книги присвячені ефективному керуванню пам’яттю, і ця область дизайну ОС постійно розвивається. Дизайн системи віртуальної пам’яті (VM), який використовує NewOS, є відносно складним, але досить простим і не особливо унікальним. Він значною мірою запозичений із UNIX/BSD. Інтерфейс API віртуальної пам’яті значною мірою базується на BeOS.

Робота VM полягає в управлінні окремими адресними просторами для кожного процесу та ядра. Кожен адресний простір розбивається на менші регіони, які є просто областями сторінок із подібними характеристиками. Регіон підтримує певний тип об’єкта зберігання VM, наприклад, файл із відображенням у пам’ять, пристрій із відображенням у пам’ять або пам’ять, підкріплену файлом підкачки. Значна частина коду VM займається налаштуванням цих складних структур даних.

Друга половина VM відповідає за обробку помилок сторінок на конкретних сторінках. У цьому випадку VM має визначити, чи завершити потік, що спричинив помилку сторінки, відобразити нову сторінку на це місце, скопіювати стару сторінку й відобразити її, викликати сторінку з файлу підкачки чи заповнити сторінку даними з файлу, відображеного в пам’ять.

Рівень файлової системи

Щоб підтримувати кілька файлових систем, а також пристрої, відображені на файлову систему, мені довелося розробити гнучкий і розширюваний рівень файлової системи. Ця область дизайну ОС дещо варіюється між різними реалізаціями. Реалізація в NewOS не є винятком, запозичуючи багато з інших реалізацій, але водночас робить дещо по-іншому.

Розташування файлової системи схоже на більшість варіантів UNIX: усі змонтовані томи розміщені в єдиному дереві, що починається з кореневої точки монтування /. За замовчуванням файлова система на базі пам’яті, rootfs, монтується в корені дерева та використовується як заповнювач для інших точок монтування.

Ще одна схожість із UNIX — розміщення файлів пристроїв у каталозі /dev/. Однак NewOS відрізняється від інших варіантів UNIX тим, що змушує сам драйвер пристрою надавати код файлової системи та точку монтування в ієрархії /dev/. Як наслідок, у працюючій системі NewOS присутні численні різні файлові системи. Інтерфейс файлової системи досить простий, і багато спільних функцій можуть використовуватися кількома файловими системами, щоб зменшити накладні витрати на пам’ять.

API, який має реалізувати файлова система, відносно простий. Наразі файлова система повинна надавати 12 викликів, більшість із яких реалізовані в парному вигляді, як-от open/close чи read/write. Окрема файлова система може не реалізовувати деякі виклики, наприклад read або write, і в такому випадку рівень файлової системи надасть стандартну реалізацію.

Основна відмінність у API файлової системи NewOS — це визначення файлового потоку. Окремий файл у NewOS має велику гнучкість у тому, що можна відкрити чи обробити в цьому файлі. У традиційній системі UNIX файл — це послідовність байтів, тобто єдиний потік, який можна відкрити та маніпулювати. У NewOS же файл може мати будь-яку кількість іменованих потоків, що розрізняються за назвою, за замовчуванням — порожній потік "". Крім того, потрібен 32-бітний ідентифікатор типу потоку з кількома стандартними константами типу потоку, такими як STREAM_TYPE_FILE, STREAM_TYPE_DIR, STREAM_TYPE_DEVICE тощо. Це замінює концепцію різних режимів у UNIX і необхідність працювати з тим самим файлом через різні API залежно від режиму. У методі NewOS обробка потоків є набагато чіткішою та, зрештою, гнучкішою. Це дозволяє спростити API файлової системи в деяких аспектах, використовуючи єдиний набір маніпуляторів (open/close, read/write) для роботи з будь-яким типом потоку. Традиційні виклики UNIX opendir/closedir у цьому API відсутні. Каталог просто відкривається з типом STREAM_TYPE_DIR і обробляється через read/write на основі записів. Чи потрібна вся ця гнучкість — інше питання, але наявні однопотокові програми можуть працювати в цій системі, відкриваючи стандартний порожній потік і приховуючи ідентифікатор типу потоку шляхом реалізації open і opendir. У Лістингу 5 наведено API користувацького простору для рівня файлової системи.

На момент написання статті API файлової системи перебуває в активній розробці й може перетворитися на щось зовсім інше. Деякі необхідні виклики все ще відсутні, наприклад можливість видалення файлу. Загалом мої плани полягають у тому, щоб завершити його, реалізувавши решту необхідних викликів. Також наразі не написано жодної дискової файлової системи, тож після виявлення непередбачених перешкод може знадобитися переробка.

Майбутні плани

Ще один план на найближче майбутнє — об’єднати ідентифікатори об’єктів NewOS різних типів в єдиний простір імен. У цьому випадку простір імен складатиметься з однакової серії 32-бітних або, можливо, 64-бітних числових ідентифікаторів. Це стосуватиметься файлових дескрипторів, ідентифікаторів семафорів, ідентифікаторів регіонів/адресних просторів, а також ідентифікаторів потоків і процесів. Це спрощує багато речей, наприклад пошук ресурсів під час завершення процесу чи обмін об’єктами між процесами.

Крім того, я хотів би додати можливість чекати або сигналізувати кільком об’єктам одночасно. Це частково реалізовано в UNIX через виклик select і повністю реалізовано в операційній системі Windows. Гнучкість, яку це приносить, величезна. Поточна схема передбачає блокування одного потоку на одному об’єкті, найчастіше семафорі. Реалізація великих серверів чи інших складних програм зазвичай передбачає створення занадто великої кількості потоків для блокування на об’єктах, що стає дуже неефективним.

Висновок

NewOS пройшов довгий шлях за короткий час свого існування. Попереду ще багато роботи, перш ніж він стане по-справжньому корисним інструментом, але цей день неухильно наближається. Основна мета проєкту NewOS, однак, — отримувати задоволення від його реалізації, випробовувати нові ідеї та, сподіваюся, слугувати джерелом інформації та натхнення для інших "домашніх" операційних систем.

Багато аспектів дизайну NewOS тут не розглянуто, і багато що могло змінитися з моменту написання статті. Щоб бути в курсі розвитку проєкту NewOS і отримати додаткову інформацію та вихідний код, відвідайте newos.org.

Лістінг 1

proc_id proc_create_proc(const char *path, const char *name, int priority); int proc_kill_proc(proc_id id); int proc_wait_on_proc(proc_id id, int *retcode); thread_id thread_create_user_thread(char *name, proc_id pid, int priority, addr entry); thread_id thread_create_kernel_thread(const char *name, int (*func)(void), int priority); int thread_suspend_thread(thread_id id); int thread_resume_thread(thread_id id); void thread_snooze(time_t time); void thread_exit(int retcode); thread_id thread_get_current_thread_id(); int thread_wait_on_thread(thread_id id, int *retcode);

Лістінг 2

typedef int (*timer_callback)(void *); typedef enum { TIMER_MODE_ONESHOT = 0, TIMER_MODE_PERIODIC } timer_mode; typedef struct timer_event { struct timer_event *next; timer_mode mode; time_t sched_time; time_t periodic_time; timer_callback func; void *data; } timer_event; // Користувач надає структуру таймера void timer_setup_timer(timer_callback func, void *data, timer_event *event); int timer_set_event(time_t relative_time, timer_mode mode, timer_event *event); int timer_cancel_event(timer_event *event);

Лістінг 3

#define SEM_FLAG_NO_RESCHED 1 // Змушує sem_release_etc не переплановувати #define SEM_FLAG_TIMEOUT 2 sem_id sem_create(int count, const char *name); int sem_delete(sem_id id); int sem_delete_etc(sem_id id, int return_code); int sem_acquire(sem_id id, int count); int sem_acquire_etc(sem_id id, int count, int flags, time_t timeout, int *deleted_retcode); int sem_release(sem_id id, int count); int sem_release_etc(sem_id id, int count, int flags);

Лістінг 4

// Блокування має бути попередньо ініціалізоване значенням 0 void acquire_spinlock(int *lock); void release_spinlock(int *lock);

Лістінг 5

typedef enum { STREAM_TYPE_NULL = 0, STREAM_TYPE_FILE, STREAM_TYPE_DIR, STREAM_TYPE_DEVICE, STREAM_TYPE_STRING } stream_type; typedef enum { SEEK_SET = 0, SEEK_CUR, SEEK_END } seek_type; int open(const char *path, const char *stream, stream_type type); int seek(int fd, off_t pos, seek_type seek_type); int read(int fd, void *buf, off_t pos, size_t *len); int write(int fd, const void *buf, off_t pos, size_t *len); int ioctl(int fd, int op, void *buf, size_t len); int close(int fd); int create(const char *path, const char *stream, stream_type type); // Не завершено, потрібна можливість видалення файлів тощо